package 记忆化搜索;

import java.util.Arrays;

//62 不同路径（使用二维数组作为缓存即可）
public class Solution4 {
    public int uniquePaths(int m, int n) {
        dp = new int[m][n];
        for(int i = 0;i<m;i++){
            Arrays.fill(dp[i],-1);
        }
        return dfs(0,0,m,n);
    }
    int[][] dp;
    int dfs(int row, int col, int m, int n){
        if(row==m||col==n) return 0;
        if(dp[row][col]!=-1) return dp[row][col];
        if(row==m-1&&col==n-1) return 1;
        return dp[row][col]=dfs(row+1,col,m,n)+dfs(row,col+1,m,n);
    }
}
